package version2024.medium;

import java.util.*;

/**
 * @author sunhl
 * @Description: HJ77 火车进站 栈
 * @Date: created in 2025/1/7 星期二 17:12
 * @Modified By:
 */
public class HJ77_TrainArriving {
    public static List<String> l = new ArrayList<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            l.clear();

            int nums = in.nextInt();
            int[] id = new int[nums];
            Stack<Integer> stack = new Stack<>();

            for (int i = 0; i < nums; i++) {
                id[i] = in.nextInt();
            }

            trainOut(id, 0, stack, "", 0);

            //对结果集排序
            Collections.sort(l);
            for (String str : l) {
                System.out.println(str);
            }
        }
    }

    /**
     * stack要么进，要么出。先进一个，处理完这个进的，然后恢复原样；再出，处理完这个出的，就完事了。
     *
     * @param id  编号数组
     * @param i   入栈次数
     * @param s   核心栈
     * @param str 存储出栈顺序的字符串
     * @param n   出栈次数
     */
    public static void trainOut(int[] id, int i, Stack<Integer> s, String str,
                                int n) {
        // 如果出栈数字已经满了，满足退出条件
        if (n == id.length) {
            l.add(str);
            return;
        }

        //如果出栈的数字没有满，此时可以出栈也可以进栈，都可以。
        //这里先做出栈
        //出栈需要建立在栈本身不为空的基础上
        if (!s.empty()) {
            int temp = s.pop();
            // 继续后面的动作，一条路走到黑
            // 出栈，该数组添加到temp
            trainOut(id, i, s, str + temp + " ", n + 1);
            // 恢复现场
            s.push(temp);
        }

        //开始做入栈场景
        //入账时要确保还有数据入账
        if (i < id.length) {
            s.push(id[i]);
            //继续后面的操作，一条路走到黑
            //i位置移动到下一个
            trainOut(id, i + 1, s, str, n);
            //恢复现场
            s.pop();
        }
    }
}
